# Read the Solution [Here](https://quastor.org/cracking-the-coding-interview/arrays-and-strings/palindrome-permutation)

# Palindrome Permutation

## Cracking the Coding Interview (CTCI) 1.4

<br />

## Question

You are given a string. Write a function that checks if the letters in the string can be rearranged to form a palindrome (or if the input is already a palindrome). You can ignore spaces in the string.

```
Input - "car race"
Output - True (the letters can be rearranged to " racecar")
```

<details>
  <summary>Solution</summary>


In order to solve this, we need to think about the properties of a palindrome. You should write a couple of palindromes down and see if you can notice any patterns.

<br />


If a string can be rewritten as a palindrome, then it either

- has an even number of characters. Ex. `caac` a - 2, c - 2
- has an odd number of characters, where there's only one character that appears an odd number of times. Ex. `cabbbac` a - 2, b - 3, c - 2

<br />

In other words, a palindrome is a string that can be reversed to produce the same string. That means that either every character has a matching pair, or there is only one character that appears an odd number of times (and that character will be placed in the middle of the string for the palindrome).

<br />

We can count the number of occurrences of each character with a dictionary. If the counts of each character satisfy our condition, then we return `True`.

<br />

The time complexity is $$O(n)$$ and the space complexity is $$O(n)$$

```python
def checkPermutation(s):
    counts = {}
    for i in s:
        if i == " ":
            continue
        counts[i] = counts.get(i, 0) + 1
    hasOdd = False
    for value in counts.values():
        if value % 2 == 1:
            if hasOdd:
                # we have more than one char
                # that appears an odd number
                # of times
                return False
            hasOdd = True

    return True
```

<a href="https://repl.it/@quastortech/Solution-2#main.py" target="_blank">Here's a Python 3 REPL with the solution and test cases.</a>

</details>